#include<iostream>
#include<vector>
#include<algorithm>
#include <iterator>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        for (int i = 0; i < numbers.size()-1; i++) {
            int diff = target - numbers[i];
            for (int j = i + 1; j < numbers.size(); j++) {
                if (numbers[j] == diff) {
                    res.push_back(i + 1);
                    res.push_back(j + 1);
                    return res;
                }
                else if (numbers[j] > diff)
                    break;
            }
        }
        return res;
    }

    vector<int> twoSumDP(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target)
                return { left + 1,right + 1 };
            else if (sum < target)
                left++;
            else
                right--;
        }
        return { -1,0 };
    }
};

int main() {
    vector<int> arr = { 2,7,11,15 };
    vector<int>::iterator it=find(arr.begin(), arr.end(), 7);
    if (it==arr.end()) {
        cout << "No match" << endl;
    }
    else {
        int ans = it - arr.begin();
        cout << ans;
    }
    Solution s;
    vector<int> arr2 = { -1,0 };
    vector<int> res = s.twoSumDP(arr, 9);
    return 0;
}